#include <stdio.h>
#define VERTICES 6

int find_root(int x, int parent[]) {
	if (parent[x] == -1) return x;
	return find_root(parent[x], parent);
}

// 1 - union successfully	0 - failed
int union_vertices(int x, int y, int parent[], int rank[])
{
	int x_root = find_root(x, parent);
	int y_root = find_root(y, parent);
	if (x_root == y_root) {
		return 0;
	} else {
		// 用rank辅助进行路径压缩
		if (rank[y_root] < rank[x_root]) {
			parent[y_root] = x_root;
		}
		else if (rank[x_root] < rank[y_root]){
			parent[x_root] = y_root;
		}
		else {
			parent[x_root] = y_root;
			rank[y_root]++;
		}
		return 1;
	}
}

void main()
{
	int i, x, y;
	int parent[VERTICES] = {-1};	//不能这样初始化，结果是{-1, 0, 0, 0, 0, 0} 
	int rank[VERTICES] = {0};	//每个顶点的高度
	for (i = 0; i < VERTICES; i++) {
		parent[i] = -1;
	}
	// int edge[6][2] = {
	// 	{0, 1}, {1, 3}, {1, 2},
	// 	{2, 4}, {3, 4}, {2, 5}
	// };
	int edge[5][2] = {	//no cycle
		{0, 1}, {1, 2},
		{2, 4}, {3, 4}, {2, 5}
	};
	for (i = 0; i < 5; i++) {
		x = edge[i][0];
		y = edge[i][1];
		if (union_vertices(x, y, parent, rank) == 0) {//two vertices of edge has same root
			printf("Cycle detected!\n");
			return ;
		}
	}
	printf("No cycle found.\n");
}